The present invention relates to a data processing method and apparatus for generating a classification tree utilized to recognize a pattern such as an image, character, audio or the like.
As disclosed in reference xe2x80x9cClassification and Regression Treesxe2x80x9d by Breiman, Friedman, Olshen and Stone, it is a known method to classify a pattern by using a so-called classification tree. The method has advantages in that the recognition speed is relatively fast and that the method is applicable to recognizing any types of patterns. Therefore, the method is widely used for pattern recognition of an image, character, audio or the like.
However, the method also has a disadvantage in that generation of a classification tree, used for classifying a pattern, is time consuming. Particularly, if the number of dimensions of a characteristic value space representing the pattern is large, an extremely large amount of time is required to generate a classification tree.
For instance, for each node of the classification tree, a certain dimension of a characteristic value space is looked at, and determination is made as to whether or not the coordinate in the object dimension of the input pattern is larger/smaller than a predetermined value. The xe2x80x9cpredetermined valuexe2x80x9d used herein is normally called a xe2x80x9cthreshold value.xe2x80x9d In other words, when generating a classification tree, decision cannot be made for each node unless it is determined xe2x80x9cwhich dimension of the n dimensions should be looked at?xe2x80x9d and xe2x80x9cwhere in the coordinate axis of the object dimension the threshold value is set?xe2x80x9d More specifically, with respect to each of all dimensions (n dimensions), a threshold value that achieves highest classification efficiency is obtained (the total number of the obtained threshold values is n), and a dimension and a threshold value that can attain the highest classification efficiency among all the dimensions are obtained. In this manner, each node of the classification tree is generated.
The present invention is made in consideration of the above situation, and has as its object to provide a data processing method and apparatus which enables to generate, at high speed, a classification tree for classifying a pattern having a characteristic value expressed in a plurality of dimensions.
Another object of the present invention is to provide a data processing method and apparatus which can generate a classification tree that realizes a high recognition success rate even if the number of learning patterns provided is small.
To attain the above objects, the present invention provides a data processing method for generating a classification tree for classifying a pattern, comprising: a step of hierarchically segmenting a coordinate axis of a characteristic value space, and generating a plurality of coordinate-axis segments and threshold values corresponding to these segments; a step of generating hierarchy information indicative of coordinate-axis segments to which a characteristic value of each of a plurality of learning patterns belongs; and a step of selecting a dimension of the characteristic value space and a threshold value as a classification condition of each node of the classification tree, based on a distribution of the plurality of learning patterns in the hierarchy information.
Furthermore, in order to attain the above objects, the present invention provides a data processing method for generating a classification tree for classifying a pattern, comprising: a step of hierarchically segmenting a coordinate axis of a characteristic value space, and generating a plurality of coordinate-axis segments and threshold values corresponding to these segments; a step of deriving learning sub-patterns from each of a plurality of learning patterns, each of which is represented by combinations of dimensions of a characteristic value space; a first generating step of generating, for each of the combinations of dimensions, hierarchy information indicative of coordinate-axis segments to which a characteristic value of each of a plurality of learning sub-patterns belongs; and a second generating step of generating a classification tree for each of the combination of dimensions, by selecting a dimension of the characteristic value space and a threshold value as a classification condition of each node of the classification tree, based on a distribution of the plurality of learning patterns in the corresponding hierarchy information.
Moreover, according to another embodiment of the present invention, a data processing apparatus which realizes the aforementioned data processing method can be provided. Furthermore, according to another embodiment of the present invention, a memory medium storing control programs for causing a computer to execute the aforementioned data processing method, can be provided.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.